A particular sub-class of SIMD data-parallel processors is known as associative processors. Such processors utilise a class of memory known as associative or content-addressable memory (CAM). Such memories, as the name implies, do not operate by addressing the memory location in the conventional sense, but rather they compare the stored contents of a pre-defined field (or set of bits) of all memory words with a global bit pattern (comprising one or more bits). Those memory words which match the applied pattern during the operation (which is variously known as searching, matching or tagging) are marked in some way (tagged) in order that they might subsequently participate in a later operation which will, in some manner, modify the stored contents of the memory.
The internal organisation of such memories are generally classified into
1. word organised (i.e. memories whereby a bit-parallel pattern may be used as the basis of the search) and the bit-parallel comparison is carried out in a single indivisible operation, or
2. bit-serial (i.e. only a single bit may be used as the basis of the search).
In the latter class of memories, bit-parallel searches may be emulated by repeated application of bit-serial searches.
Some applications of content-addressable memories follow the search phase with a match resolution phase, whereby a single matching memory location is uniquely located (generally the first from the top) and then updated—generally in the form of a conventional memory write cycle.
Applications of content-addressable memory for parallel processing make use of a programmable multi-write opportunity, whereby the many tagged memory words may all (or a selected subset) be updated simultaneously.
The major attributes of such a memory are:                natural parallelism, whereby multiple memory words may be tagged in parallel; natural parallelism, whereby multiple memory words may be subsequently updated or modified in parallel.        
Such memories are universally implemented as either bit-serial or word-organised. Some examples of CAM bit-serial and bit-parallel data memories are provided in the following patents: U.S. Pat. No. 4,799,192 which is directed to a three transistor content addressable memory; U.S. Pat. No. 4,833,643 which concerns associative memory cells; U.S. Pat. No. 4,991,136 which is directed to a semiconductor associative memory device with memory refresh during match and read operations; and U.S. Pat. No. 4,965,767 associative memory having simplified memory cell circuitry.
Early instances of the invention have been manufactured for use with the Aspex ASP (Associative String Processor) data parallel processor. The ASP is a SIMD data processor that in typical configurations operates on 1024 to 65536 data items in parallel. Some of the invention's detail is specific to this data processor. The major attributes of the latest version of the ASP are 1152 processing elements on a single device 12.0 mm×12.0 mm in size and 100 MHz clock speed. Future versions of this processor will incorporate up to 8192 processing elements.
Conventional word-organised associative (content-addressable) memory can take many forms but a simple and common exemplary solution is now described with reference to FIG. 1. FIG. 1 shows a simple memory cell 10 which comprises a static RAM cell 12 together with a form of EXNOR network 14, which implements in use an equivalence comparison between the stored state in the RAM cell 12 and a broadcast bit value to be compared with.
The memory write cycle comprises the application of the data and NOT(data) to the bit lines 16 and a strobe on the word line 18. The memory search cycle comprises a precharge of the match line 20, with the bit lines 16 held low (to prevent a discharge path to ground), followed by the release of the precharge and the application of the search data (and NOT(data)) onto the bit lines 16. If the stored and applied data are different, then the match line 20 will discharge.
Such an organisation may be configured into a word-organised memory by simply creating a word-array on common match and word lines 18, 20. Any mismatch on any bit(s) will result in the common match line 20 discharging.
Implicit masking of any bit-column during a search cycle can be carried out by holding both the bit lines 16 low. However, there is a significant disadvantage in that this style of memory cell 10 is restricted to unconditional write of all bits of the stored data word, because of the common word line 18 (i.e. masked writes are not possible). If individual fields or bits of the memory word are to be updated, then multi-write (the capability to update more than one word at a time) is impossible. A large number of variants exist for memory cells to fulfil this role but they all suffer from the same problem.
The present invention aims to overcome this problem and provide a far more flexible solution to the existing CAMs 10 described above.